package com.tys.algorithm.advanced.test.class22;

/**
 * 返回裂开的数的种类
 * 后面的数不能比前面的数小，可以相等
 */
public class Code03_SplitNumber {

    // n为正数
    public static int ways(int n) {
        //负数返回0
        if (n < 0) {
            return 0;
        }
        //1返回1
        if (n == 1) {
            return 1;
        }
        return process(1, n);
    }

    // pre: 上一个拆出来的数是pre
    // rest: 还剩rest需要去拆
    // 返回拆解的方法数
    public static int process(int pre, int rest) {
        //遵守pre<rest，最后rest剩余0
        //之前的选择就是有效方案，返回1种
        if (rest == 0) {
            return 1;
        }
        //大于时没有结果，无效的
        if (pre > rest) {
            return 0;
        }
        int ways = 0;
        //从之前的数开始试，从pre开始，不能小于等于rest
        for (int first = pre; first <= rest; first++) {
            //rest-first 剩余的
            ways += process(first, rest - first);
        }
        return ways;
    }

    public static int dp1(int n) {
        if (n < 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        //准备表
        int[][] dp = new int[n + 1][n + 1];
        //pre不为0，第一行无效
        //dp[pre][0]rest=0时pre=1
        //dp[pre][pre]对角线也是1， 8,8 依赖 8,0,
        for (int pre = 1; pre <= n; pre++) {
            dp[pre][0] = 1;
            dp[pre][pre] = 1;
        }
        //行：从下向上填
        for (int pre = n - 1; pre >= 1; pre--) {
            //列，rest<pre不用管，rest=pre不用管
            for (int rest = pre + 1; rest <= n; rest++) {
                //抄递归
                int ways = 0;
                for (int first = pre; first <= rest; first++) {
                    ways += dp[first][rest - first];
                }
                dp[pre][rest] = ways;
            }
        }
        return dp[1][n];
    }

    public static int dp2(int n) {
        if (n < 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int[][] dp = new int[n + 1][n + 1];
        for (int pre = 1; pre <= n; pre++) {
            dp[pre][0] = 1;
            dp[pre][pre] = 1;
        }
        for (int pre = n - 1; pre >= 1; pre--) {
            for (int rest = pre + 1; rest <= n; rest++) {
                //依赖下面的
                dp[pre][rest] = dp[pre + 1][rest];
                //左边rest-pre位置的
                dp[pre][rest] += dp[pre][rest - pre];
            }
        }
        return dp[1][n];
    }

    public static void main(String[] args) {
        int test = 39;
        System.out.println(ways(test));
        System.out.println(dp1(test));
        System.out.println(dp2(test));
    }

}
